#include <algorithm>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n=prices.size(), m;
        if (n<=1) return 0;
        vector<int> left(n,0);
        m=prices[0];
        for (int i=1;i<n;i++) {
            left[i]=max(left[i-1], prices[i]-m);
            m=min(m, prices[i]);
        }
        vector<int> right(n,0);
        m=prices[n-1];
        for (int i=n-2;i>=0;i--) {
            right[i]=max(right[i+1], m-prices[i]);
            m=max(m, prices[i]);
        }
        int ans=max(left[n-1], right[0]);
        for (int i=0;i<n-1;i++)
            ans=max(ans, left[i]+right[i+1]);
        return ans;
    }
};
